package xyz.sekai52799.answer.a601_a800;

import java.util.*;

public class Question710 {

//    给定一个整数 n 和一个 无重复 黑名单整数数组blacklist。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个未加入黑名单blacklist的整数。
//    任何在上述范围内且不在黑名单blacklist中的整数都应该有 同等的可能性 被返回。
//
//    优化你的算法，使它最小化调用语言 内置 随机函数的次数。
//
//    实现Solution类:
//
//    Solution(int n, int[] blacklist)初始化整数 n 和被加入黑名单blacklist的整数
//    int pick()返回一个范围为 [0, n - 1] 且不在黑名单blacklist 中的随机整数
//
//    提示:
//
//            1 <= n <= 109
//            0 <= blacklist.length <= min(105, n - 1)
//            0 <= blacklist[i] < n
//            blacklist中所有值都 不同
//            pick最多被调用2 * 104次
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode.cn/problems/random-pick-with-blacklist
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    // 这里只是名字和leetcode上的不一样，功能是一样的



    // 黑名单长度为s，我们从[0, N-s)中取随机值，这个随机值有可能在黑名单中，怎么办？
    // [0, N-s)内的元素，如果有i个在黑名单中，那么在[N-s, N)中，必定有i个元素不在黑名单中
    // 对[0, N-s)中的黑名单元素和[N-s, N)中不在黑名单中的元素做映射m，必定可以一一对应

    Map<Integer, Integer> b2w;
    Random random;
    int bound;

    public Question710(int n, int[] blacklist) {
        b2w = new HashMap<Integer, Integer>();
        random = new Random();
        int m = blacklist.length;
        bound = n - m;
        Set<Integer> black = new HashSet<Integer>();
        for (int b : blacklist) {
            if (b >= bound) {
                black.add(b);
            }
        }

        int w = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (black.contains(w)) {
                    ++w;
                }
                b2w.put(b, w);
                ++w;
            }
        }
    }

    public int pick() {
        int x = random.nextInt(bound);
        return b2w.getOrDefault(x, x);
    }
}
